//
//  main.c
//  归并排序（非递归）sort
//
//  Created by Song on 2018/4/10.
//  Copyright © 2018年 Song. All rights reserved.
//

//  有问题，未成功写出来。。

#include <stdio.h>

#define length 9

// 一次归并算法(递归与非递归均一致)
/*
    设 两个相邻的有序序列为r[s]~r[m] 和 r[m+1]~r[t], 将这两个有序序列，归并成为一个有序序列 r1[s]~r1[t]
    i,j 分别指向两个有序序列的第一个记录（i=s,j=m+1），k指向存放归并结果的位置（k=s）
    取出 i j 所指记录的较小者，存入 k 所指的位置
 */
void merge(int r[],int r1[],int s,int m,int t) {
    int i = s,j = m+1,k = s;
    while (i<=m && j<=t) { // 两个序列内进行循环
        if (r[i]<=r[j]) { // 取出r[i] r[j]中的较小者放入 r1[k]
//            r1[k++] = r[i++];
            r1[k] = r[i];
            k++;
            i++;
        }else {
            r1[k++] = r[j++];
        }
    }
    if (i<=m) { // 若第一个子序列没处理完，则进行收尾处理
        while (i<=m) {
            r1[k++] = r[i++];
        }
    }else { // 若第二个子序列没处理完，则进行收尾处理
        while (j<=t) {
            r1[k++] = r[j++];
        }
    }
}

// 一趟归并排序算法
void mergePass(int r[],int r1[], int n,int h) {
    int i = 1,k;
    while (i <= n-2*h+1) { // 待归并记录至少有两个长度为 h 的子序列
        merge(r, r1, i, i+h-1, i+2*h-1);
        i += 2*h;
    }
    if (i<n-h+1) { // 待归并序列中有一个长度小于 h
        merge(r, r1, i, i+h-1, n);
    }else { // 待归并序列中只剩一个子序列
        for (k = 1; k<=n; k++) {
            r1[k] = r[k];
        }
    }
}

// 非递归
void mergeSort1(int r[],int r1[], int n) {
    int h = 1;
    while (h<n) {
        mergePass(r, r1, n, h);
        h = 2*h;
        mergePass(r1, r, n, h);
        h = 2*h;
    }
}


int main(int argc, const char * argv[]) {
    int arr[] = {9,1,8,2,7,3,4,6,5};
    int arr1[9];
    for (int a = 0; a<length; a++) {
        printf("%d ",arr[a]);
    }
    printf("\n");
    
    mergeSort1(arr, arr1, 9);
    
    printf("fei排序后：");
    for (int a = 0; a<length; a++) {
        printf("%d ",arr1[a]);
    }
    printf("\n");
    return 0;
}
